#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
    
 };
class Solution0 {//dfs
public:
    void preorder(TreeNode*root,vector<int>&res,int pi)
    {
        if(pi==res.size())
        {
            res.push_back(root->val);
        }else
        {
            res[pi]=max(res[pi],root->val);
        }
        if(root->left)
        {
            
            preorder(root,res,pi+1);
        }
        if(root->right)
        {
            preorder(root, res,pi+1);
        }

    }
    vector<int> largestValues(TreeNode* root) {
        int i=0;
        if(!root)return {};
        vector<int>res;
        preorder(root,res,0);
        return res;
    }
};
    
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*>tree;
        vector<int>ans;
        if(root==NULL)return {};
        tree.push(root);
        int height=0;
        
        while(!tree.empty())
        {
            int Max=INT_MIN;
            height=tree.size(); 
            for(int i=1;i<=height;i++)
            {
                TreeNode*tmp=tree.front();
                tree.pop();
                Max=max(Max,tmp->val);
                if(tmp->left)tree.push(tmp->left);
                if(tmp->right)tree.push(tmp->right);
            }
            ans.push_back(Max);
        }
        return ans;
    }
};